// 链表相加（一）
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param l1 ListNode类
     * @param l2 ListNode类
     * @return ListNode类
     */
    ListNode* ListAdd(ListNode* l1, ListNode* l2)
    {
        // 1、创建哨兵位头节点
        ListNode* head, *tail;
        head = tail = new ListNode(int());
        // 2、开始相加
        int t = 0; //记录对应数位两个数字相加的结果 && 保存进位
        while(l1 || l2 || t)
        {
            // 先加上第一个链表
            if(l1)
            {
                t += l1->val;
                l1 = l1->next;
            }
            // 加上第二个链表
            if(l2)
            {
                t += l2->val;
                l2 = l2->next;
            }
            // 处理本次数位的相加结果
            ListNode* tmp = new ListNode(t % 10);
            tail->next = tmp;
            tail = tmp;
            t /= 10;
        }
        // 3、返回结果（防止内存泄漏，记得把哨兵位头节点干掉）
        ListNode* ans = head->next;
        delete head;
        return ans;
    }
};